from collections import Counter
from typing import List


# 30. 串联所有单词的子串
# 给定一个字符串 s 和一个字符串数组 words。 words 中所有字符串 长度相同。
# s 中的 串联子串 是指一个包含  words 中所有字符串以任意顺序排列连接起来的子串。

def findSubstring(s: str, words: List[str]) -> List[int]:
    # 单词长度
    word_len = len(words[0])
    # 单词个数
    word_size = len(words)

    words_counter = Counter(words)

    # 字符串长度
    s_len = len(s)

    re = list()

    for start_index in range(word_len):
        # 存放每个单词出现的次数
        word_dict = {}
        word_count = 0
        current_start = start_index
        #
        while current_start + word_len <= s_len:
            # 当前单词
            current_word = s[current_start:current_start + word_len]

            # 单词数量不够
            current_word_count = word_dict.get(current_word, 0)
            word_dict[current_word] = current_word_count + 1

            word_count += 1
            current_start += word_len

            # 移除前面那个
            if word_count > word_size:
                del_index = current_start - word_len * (word_size + 1)
                if del_index >= 0:
                    del_word = s[del_index:del_index + word_len]
                    del_word_count = word_dict.get(del_word, 0)
                    if del_word_count == 1:
                        word_dict.pop(del_word)
                    else:
                        word_dict[del_word] = del_word_count - 1
                    word_count -= 1
            # 判断是否相等
            if word_count == word_size and word_dict == words_counter:
                re.append(current_start - (word_len * word_size))

    return re


# 耗时很长
def findSubstring_longTime(s: str, words: List[str]) -> List[int]:
    # 单词长度
    word_len = len(words[0])
    # 单词个数
    word_size = len(words)

    # 字符串长度
    s_len = len(s)

    # 最后一位数的指针
    total_word_len = word_len * word_size

    # 结果
    re_list = list()

    start_index = 0

    while start_index + total_word_len <= s_len:
        # 当前单词
        current_window = s[start_index:start_index + total_word_len]
        # 将窗口拆分成单词
        # 耗时操作
        current_window_list = [current_window[i:i + word_len] for i in range(0, total_word_len, word_len)]
        # 判断两个结合中的元素是否相同
        # 注意：集合中包含重复的元素，相同元素出现的次数也需要相同
        # 耗时操作
        if Counter(words) == Counter(current_window_list):
            re_list.append(start_index)

        # 每次向右滑动一次
        start_index += 1

    return re_list


s_1 = "wordgoodgoodgoodbestword"
words_1 = ["word", "good", "best", "good"]
result = findSubstring(s_1, words_1)
print(f"result:{result}")

s_1 = "barfoofoobarthefoobarman"
words_1 = ["bar", "foo", "the"]
result = findSubstring(s_1, words_1)
print(f"result:{result}")

s_1 = "barfoothefoobarman"
words_1 = ["foo", "bar"]
result = findSubstring(s_1, words_1)
print(f"result:{result}")

s_1 = "wordgoodgoodgoodbestword"
words_1 = ["word", "good", "best", "word"]
result = findSubstring(s_1, words_1)
print(f"result:{result}")
